package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/10/20 10:44
 **/
public class Day48_1_Num779_KthGrammar {
    class Solution {
        public int kthGrammar(int n, int k) {
            if(n == 1) return 0;
            int fa = kthGrammar(n-1, ((k+1)/2));
            return (k & 1) == 1 ? fa : 1 ^ fa;
        }
    }
    class Solution2 {
        public int kthGrammar(int n, int k) {
            if(n == 1) return 0;
            int mid = (int)Math.pow(2, n-1-1);
            if(k <= mid){
                return kthGrammar(n-1, k);
            }
            return 1 ^ kthGrammar(n-1, k - mid);
        }
    }
}